#pragma once
#include <iostream>
#include <vector>
#include <map>
#include <climits>
#include <queue>
#include <cstring>
#include <string>
#include <stack>
#include <functional>
using namespace std;
#include "UnionFindSet.h"
// 邻接矩阵
namespace matrix
{
    // 无向
    // V 顶点 W 边
    template <class V, class W, W MAX_W = INT_MAX, bool Direction = false>
    class Graph
    {
        typedef Graph<V, W, MAX_W, Direction> Self;

    public:
        Graph() {}
        Graph(const V *a, size_t n)
        {
            _vertexs.reserve(n);
            for (size_t i = 0; i < n; i++)
            {
                _vertexs.push_back(a[i]);
                _indexMap[a[i]] = i;
            }
            _matrix.resize(n);
            for (int i = 0; i < n; i++)
            {
                _matrix[i].resize(n, MAX_W);
            }
        }

        struct Edge
        {
            int _srci;
            int _dsti;
            W _w;
            Edge(int srci, int dsti, W &w)
                : _srci(srci), _dsti(dsti), _w(w)
            {
            }
            bool operator>(const Edge &e) const
            {
                return _w > e._w;
            }
        };
        void Dijkstra(const V &src, vector<W> &dist, vector<int> &parentPath)
        {
            int srci = GetVertexIndex(src);
            int n = _vertexs.size();
            dist.resize(n, MAX_W);
            parentPath.resize(n, -1);
            dist[srci] = 0;
            vector<bool> S(n, false); // 确定路径的顶点集合
            for (int j = 0; j < n; j++)
            {

                W min = MAX_W;
                int u = 0;
                for (size_t i = 0; i < n; i++)
                {
                    if (!S[i] && dist[i] < min)
                    {
                        min = dist[i];
                        u = i;
                    }
                }
                S[u] = true;
                for (size_t k = 0; k < n; k++)
                {
                    if ((S[k] == false && _matrix[u][k] != MAX_W) && dist[k] > dist[u] + _matrix[u][k])
                    {
                        dist[k] = dist[u] + _matrix[u][k];
                        parentPath[k] = u;
                    }
                }
            }
        }
        W Prim(Self &midTree, const V &src)
        {
            int srci = GetVertexIndex(src);
            int n = _vertexs.size();
            midTree._vertexs = _vertexs;
            midTree._indexMap = _indexMap;
            midTree._matrix.resize(n);
            for (int i = 0; i < n; i++)
            {
                midTree._matrix[i].resize(n, MAX_W);
            }
            priority_queue<Edge, vector<Edge>, greater<Edge>> minq;
            vector<bool> X(n, false);
            vector<bool> Y(n, true);
            X[srci] = true;
            Y[srci] = false;
            for (int i = 0; i < n; i++)
            {
                if (_matrix[srci][i] != MAX_W)
                    minq.push(Edge(srci, i, _matrix[srci][i]));
            }
            int size = 0;
            W totalW = W();
            while (size < n - 1 && !minq.empty())
            {
                Edge eg = minq.top();
                minq.pop();
                if (X[eg._dsti])
                {
                    cout << "构成环";
                    cout << _vertexs[eg._srci] << ":" << _vertexs[eg._dsti] << "->" << eg._w << endl;
                }
                else
                {
                    midTree._AddEdge(eg._srci, eg._dsti, eg._w);
                    cout << _vertexs[eg._srci] << ":" << _vertexs[eg._dsti] << "->" << eg._w << endl;

                    totalW += eg._w;
                    size++;
                    X[eg._dsti] = true;
                    Y[eg._dsti] = false;
                    for (int i = 0; i < n; i++)
                    {
                        if (_matrix[eg._dsti][i] != MAX_W && Y[i])
                        {
                            minq.push(Edge(eg._dsti, i, _matrix[eg._dsti][i]));
                        }
                    }
                }
            }
            if (size == n - 1)
            {
                return totalW;
            }
            else
            {
                return W();
            }
        }
        W Kruskal(Self &midTree)
        {
            int n = _vertexs.size();
            midTree._vertexs = _vertexs;
            midTree._indexMap = _indexMap;
            midTree._matrix.resize(n);
            for (int i = 0; i < n; i++)
            {
                midTree._matrix[i].resize(n, MAX_W);
            }

            priority_queue<Edge, vector<Edge>, greater<Edge>> minq;
            UnionFindSet ufs(n);
            W ret = W();
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (i < j && _matrix[i][j] != MAX_W)
                    {
                        minq.push(Edge(i, j, _matrix[i][j]));
                    }
                }
            }
            int size = 0;
            while (!minq.empty())
            {
                Edge eg = minq.top();
                minq.pop();
                if (!ufs.IsInSet(eg._srci, eg._dsti))
                {
                    midTree._AddEdge(eg._srci, eg._dsti, eg._w);
                    ufs.Union(eg._srci, eg._dsti);
                    size++;
                    ret += eg._w;
                }
            }
            if (size == n - 1)
            {
                return ret;
            }
            else
            {
                return W();
            }
        }

        size_t GetVertexIndex(const V &v)
        {
            auto it = _indexMap.find(v);
            if (it != _indexMap.end())
            {
                return it->second; //
            }
            else
            {
                return -1;
            }
        }
        void _AddEdge(size_t srci, size_t dsti, const W &w)
        {
            _matrix[srci][dsti] = w;
            // 无向图
            if (Direction == false)
            {
                _matrix[dsti][srci] = w;
            }
        }
        void AddEdge(const V &src, const V &dst, const W &w)
        {
            size_t srci = GetVertexIndex(src);
            size_t dsti = GetVertexIndex(dst);
            _AddEdge(srci, dsti, w);
        }
        void BFS(const V &src)
        {
            int srci = GetVertexIndex(src);
            queue<int> q;
            int n = _vertexs.size();
            vector<bool> visited(n, false);
            q.push(srci);
            visited[srci] = true;
            int levelsize = 1;
            while (!q.empty())
            {
                for (int i = 0; i < levelsize; i++)
                {
                    int front = q.front();
                    q.pop();
                    cout << front << ":" << _vertexs[front] << " ";
                    for (size_t i = 0; i < n; i++)
                    {
                        if (_matrix[front][i] != MAX_W && visited[i] == false)
                        {
                            q.push(i);
                            visited[i] = true;
                        }
                    }
                }
                cout << endl;
                levelsize = q.size();
            }
        }
        void dfs(int srci, vector<bool> &visited)
        {
            cout << srci << ":" << _vertexs[srci] << " ";
            visited[srci] = true;
            for (size_t i = 0; i < _vertexs.size(); i++)
            {
                if (_matrix[srci][i] != MAX_W && visited[i] == false)
                {
                    dfs(i, visited);
                }
            }
        }
        void DFS(const V &src)
        {
            int srci = GetVertexIndex(src);
            vector<bool> visited(_vertexs.size(), false);
            dfs(srci, visited);
            for (int i = 0; i < visited.size(); i++)
            {
                if (visited[i] == false)
                {
                    dfs(i, visited);
                }
            }
        }
        void Print()
        {
            // 顶点
            for (size_t i = 0; i < _vertexs.size(); i++)
            {
                cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
            }
            cout << endl;
            // 横下标
            cout << "  ";
            for (int i = 0; i < _vertexs.size(); i++)
            {
                printf("%4d", i);
            }
            cout << endl;

            for (int i = 0; i < _matrix.size(); i++)
            {
                cout << i << " "; // 纵下标
                for (int j = 0; j < _matrix[i].size(); j++)
                {
                    if (_matrix[i][j] == MAX_W)
                        printf("%4c", '*');
                    else
                        printf("%4d", _matrix[i][j]);
                }
                cout << endl;
            }
        }
        void PrinrtShotPath(const V &src, const vector<W> &dist, const vector<int> &parentPath)
        {
            size_t srci = GetVertexIndex(src);
            size_t n = _vertexs.size();
            for (size_t i = 0; i < n; i++)
            {
                if (i == srci)
                    continue;
                vector<int> pPath;
                size_t parenti = i;
                while (parenti != srci)
                {
                    pPath.push_back(parenti);
                    parenti = parentPath[parenti];
                }
                pPath.push_back(srci);
                reverse(pPath.begin(), pPath.end());
                for (auto e : pPath)
                {
                    cout << _vertexs[e] << "->";
                }
                cout << dist[srci] << endl;
            }
        }
        void FloydWarShall(vector<vector<W>> &vvDist, vector<vector<int>> &vvParentPath)
        {
            size_t n = _vertexs.size();
            vvDist.resize(n);
            vvParentPath.resize(n);
            for (size_t i = 0; i < n; i++)
            {
                vvDist[i].resize(n, MAX_W);
                vvParentPath[i].resize(n, -1);
            }
            for (size_t i = 0; i < n; i++)
            {
                for (size_t j = 0; j < n; j++)
                {
                    if (_matrix[i][j] != MAX_W)
                    {
                        vvDist[i][j] = _matrix[i][j];
                        vvParentPath[i][j] = i;
                    }
                    if (i == j)
                    {
                        vvDist[i][j] = W();
                    }
                }
            }
            for (size_t k = 0; k < n; k++)
            {
                for (size_t i = 0; i < n; i++)
                {
                    for (size_t j = 0; j < n; j++)
                    {
                        if (vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W && vvDist[i][j] > vvDist[i][k] + vvDist[k][j])
                        {
                            vvDist[i][j] = vvDist[i][k] + vvDist[k][j];
                            vvParentPath[i][j] = vvParentPath[k][j];
                        }
                    }
                }
            }
        }
        // dfs邻接矩阵拓扑排序
        void DFSSort(int i, vector<bool> &visited, stack<int> &s)
        {
            visited[i] = true;
            for (int j = 0; j < _vertexs.size(); j++)
            {
                if (_matrix[i][j] != MAX_W && visited[j] == false)
                    DFSSort(j, visited, s);
            }
            s.push(i);
        }
        void DFSTopologicalsort(const V &src)
        {
            size_t srci = GetVertexIndex(src);
            size_t n = _vertexs.size();
            vector<bool> visited(n, -1);
            stack<int> s;
            DFSSort(srci, visited, s);
            for (size_t i = 0; i < n; i++)
            {
                if (visited[i] == false)
                    DFSSort(i, visited, s);
            }
        }
        // dfs邻接矩阵逆拓扑排序
        void DFSSortreverse(int i, vector<bool> &visited)
        {
            visited[i] = true;
            for (int j = 0; j < _vertexs.size(); j++)
            {
                if (_matrix[i][j] != MAX_W && visited[j] == false)
                    DFSSort(j, visited, s);
            }
            cout << i << endl;
        }
        // Kahn算法<入度法>拓扑排序
        vector<int> topologicalSort()
        {
            vector<int> ret;
            ret.resize(n);
            size_t n = _vertexs.size();
            vector<int> inDegree(n, 0); // 入度数组
            for (size_t i = 0; i < n; i++)
            {
                for (size_t j = 0; j < n; j++)
                {
                    if (_matrix[j][i] != MAX_W)
                    {
                        inDegree[i]++;
                    }
                }
            }
            queue<int> q;
            for (size_t i = 0; i < n; i++)
            {
                if (inDegree[i] == 0)
                    q.push(i);
            }
            while (!q.empty())
            {
                int top = q.front();
                q.pop();
                // 访问
                ret.push_back(top);
                for (size_t i = 0; i < n; i++)
                {
                    if (_matrix[top][i] != MAX_W)
                        inDegree[i]--;
                    if (inDegree[i] == 0)
                        q.push(i);
                }
            }
            if (ret.size() != n)
            {
                return {};
            }
            return ret;
        }

    private:
        vector<V> _vertexs;        // 顶点集合
        map<V, int> _indexMap;     // 顶点映射下标
        vector<vector<W>> _matrix; // 邻接矩阵
    };
    void TestGraph1()
    {
        Graph<char, int, INT_MAX, true> g("0123", 4);
        g.AddEdge('0', '1', 1);
        g.AddEdge('0', '3', 4);
        g.AddEdge('1', '3', 2);
        g.AddEdge('1', '2', 9);
        g.AddEdge('2', '3', 8);
        g.AddEdge('2', '1', 5);
        g.AddEdge('2', '0', 3);
        g.AddEdge('3', '2', 6);
        g.Print();
    }
    void TestDBfs()
    {
        string a[] = {"张三", "李四", "王五", "赵六", "周七"};
        Graph<string, int> g1(a, sizeof(a) / sizeof(string));
        g1.AddEdge("张三", "李四", 100);
        g1.AddEdge("张三", "王五", 200);
        g1.AddEdge("王五", "赵六", 30);
        g1.AddEdge("王五", "周七", 30);
        g1.Print();
        g1.BFS("张三");
        g1.DFS("张三");
    }
    void TestGraphMinTree()
    {
        const char *str = "abcdefghi";
        Graph<char, int> g(str, strlen(str));
        g.AddEdge('a', 'b', 4);
        g.AddEdge('a', 'h', 8);
        g.AddEdge('b', 'c', 8);
        g.AddEdge('b', 'h', 11);
        g.AddEdge('c', 'i', 2);
        g.AddEdge('c', 'f', 4);
        g.AddEdge('c', 'd', 7);
        g.AddEdge('d', 'f', 14);
        g.AddEdge('d', 'e', 9);
        g.AddEdge('e', 'f', 10);
        g.AddEdge('f', 'g', 2);
        g.AddEdge('g', 'h', 1);
        g.AddEdge('g', 'i', 6);
        g.AddEdge('h', 'i', 7);
        // Graph<char, int> kminTree;
        // cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
        // kminTree.Print();
        Graph<char, int> PminTree;
        cout << "Prim:" << g.Prim(PminTree, 'a') << endl;
        PminTree.Print();
    }
}

// 邻接表
namespace link_table
{
    template <class W>
    struct Edge
    {
        Edge(int dsti, const W &w) : _dsti(dsti), _w(w), _next(nullptr) {}

        int _dsti;      // 目标点的下标
        W _w;           // 权值
        Edge<W> *_next; // 连接指针
    };
    template <class V, class W, bool Direction = false>
    class Graph
    {
    public:
        typedef struct Edge<W> Edge;
        Graph(const V *a, size_t n)
        {
            _vertexs.reserve(n);
            for (size_t i = 0; i < n; i++)
            {
                _vertexs.push_back(a[i]);
                _indexMap[a[i]] = i;
            }
            _tables.resize(n, nullptr);
        }
        size_t GetVertexIndex(const V &v)
        {
            auto it = _indexMap.find(v);
            if (it != _indexMap.end())
            {
                return it->second; //
            }
            else
            {
                return -1;
            }
        }
        void AddEdge(const V &src, const V &dst, const W &w)
        {
            size_t srci = GetVertexIndex(src);
            size_t dsti = GetVertexIndex(dst);
            Edge *eg = new Edge(dsti, w);
            eg->_next = _tables[srci];
            _tables[srci] = eg;
            if (Direction == false)
            {
                Edge *eg1 = new Edge(srci, w);
                eg1->_next = _tables[dsti];
                _tables[dsti] = eg1;
            }
        }
        void Print()
        {
            // 顶点
            for (size_t i = 0; i < _vertexs.size(); i++)
            {
                cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
            }
            cout << endl;
            for (size_t i = 0; i < _tables.size(); i++)
            {
                cout << _vertexs[i] << "[" << i << "]->";
                Edge *cur = _tables[i];
                while (cur)
                {
                    cout << _vertexs[cur->_dsti] << "[" << cur->_dsti << "]" << ":" << cur->_w << "-> ";
                    cur = cur->_next;
                }
                cout << "nullptr" << endl;
            }
        }
        void BFS(const V &src)
        {
            int srci = GetVertexIndex(src);
            int n = _vertexs.size();
            vector<bool> visited(n, false);
            queue<int> q;

            q.push(srci);
            visited[srci] = true;
            while (!q.empty())
            {
                int front = q.front();
                q.pop();
                cout << front << ":" << _vertexs[front] << " ";
                Edge *cur = _tables[front];
                while (cur)
                {
                    if (visited[cur->_dsti] == false)
                    {
                        q.push(cur->_dsti);
                        visited[cur->_dsti] = true;
                    }
                    cur = cur->_next;
                }
            }
        }
        void dfs(int srci, vector<bool> &visited)
        {
            cout << srci << ":" << _vertexs[srci] << " ";
            visited[srci] = true;
            Edge *cur = _tables[srci];
            while (cur)
            {
                if (visited[cur->_dsti] == false)
                {
                    dfs(cur->_dsti, visited);
                }
                cur = cur->_next;
            }
        }
        void DFS(const V &src)
        {
            int srci = GetVertexIndex(src);
            vector<bool> visited(_vertexs.size(), false);
            dfs(srci, visited);
            for (int i = 0; i < visited.size(); i++)
            {
                if (visited[i] == false)
                {
                    dfs(i, visited);
                }
            }
        }

    private:
        vector<V> _vertexs;     // 顶点集合
        map<V, int> _indexMap;  // 顶点映射下标
        vector<Edge *> _tables; // 邻接表
    };
    void TestGraph1()
    {
        string a[] = {"张三", "李四", "王五", "赵六", "周七"};
        Graph<string, int> g1(a, sizeof(a) / sizeof(string));
        g1.AddEdge("张三", "李四", 100);
        g1.AddEdge("张三", "王五", 200);
        g1.AddEdge("王五", "赵六", 30);
        g1.AddEdge("王五", "周七", 30);
        g1.Print();
        g1.BFS("张三");
        g1.DFS("张三");
    }
}
